#include<bits/stdc++.h>
using namespace std;
const int N=15,mod=1e9+7;
int n,T,sz,ans;
string c,f[N];
bool check(int x,int l)
{
	for(int i=0;i<l;i++)
		if(f[n][x+i]!=c[i]) return 0;
	return 1;
}
int main()
{
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	cin>>n>>T;
	f[1]="0",f[2]="1";
	for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];
	sz=f[n].size();
	for(int i=1,t;i<=T;i++)
	{
		cin>>c;t=c.size();ans=0;
		for(int j=t-1;j<sz;j++)
			ans+=check(j-t+1,t);
		cout<<ans<<'\n';
	}
	fclose(stdin);fclose(stdout);
	return 0;
}
